import java.util.HashMap;
import java.util.Map;

public class O55 {
    int max,min;
    public int maxDepth(TreeNode root) {
        if (root==null)
            return 0;
        return Math.max(maxDepth(root.right),maxDepth(root.left))+1;
    }
    Map<TreeNode,Integer> map = new HashMap<>();
    public boolean isBalanced(TreeNode root) {
        if (root==null)
            return true;
        return Math.abs(dfs(root.left)-dfs(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
    int dfs(TreeNode root){
        if (root==null)
            return 0;
        if (map.containsKey(root))
            return map.get(root);
        else {
            int t = Math.max(dfs(root.right),dfs(root.left))+1;
            map.put(root,t);
            return t;
        }
    }
}
